package com.company.algo.graph;

import java.util.Arrays;
import java.util.HashMap;

public class NetworkDelayTime {
    int N = 110, M = 6010;
    int[][] w = new int[N][N];
    int[] dist = new int[N];
    boolean[] visited = new boolean[N];
    int INF = 0x3f3f3f3f;
    int n,k;
    //Dijkstra
    public int networkDelayTime(int[][] times, int _n, int _k) {
        n = _n;k=_k;
        //初始化每个起点到任意终点的距离
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                w[i][j] = w[j][i] = i == j ? 0:INF;
            }
        }
        for(int[] t:times){
            int u=t[0],v=t[1],c=t[2];
            w[u][v] = c;
        }
        //dijkstra算法
        dijkstra();
        //从所有最短路径中取max即为从k点出发，到其他点的最短路径的最大值
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans,dist[i]);
        }
        return ans > INF/2 ? -1 : ans;
    }
    void  dijkstra(){
        Arrays.fill(visited,false);
        Arrays.fill(dist,INF);
        dist[k] = 0;
        while (true){
            //1.在没有访问过的点中找一个顶点min_idx使得dis[min_idx]最小
            int min_idx = 0, min_w = Integer.MAX_VALUE >> 2;
            for (int j = 1; j <= n; j++) {
                if (!visited[j] && min_w > dist[j]){
                    min_idx = j;
                    min_w =dist[j];
                }
            }
            if (min_idx == 0) return;        //如果没有可选的点，直接结束
            //2.min_idx标记为已确认最短路径
            visited[min_idx] = true;
            //3.For与min_idx相连的每个未确认最短路径的顶点
            for (int i = 1; i <= n; i++) {
                if (!visited[i] && dist[i]>dist[min_idx]+w[min_idx][i]){
                    dist[i] = dist[min_idx]+w[min_idx][i];
                }
            }
        }
    }
}
